// 序列化二叉树与反序列化二叉树 --> 序列化是将二叉树按一定规则存储为字符串，反序列化是将其返回为一个树结构
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/


// ========================按前序遍历进行序列化与反序列化============================
 /**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  let strArr = [];
  let encodeTree = (node) => {
      if (!node) {
          strArr.push('#');
          return;
      }
      strArr.push(node.val);
      encodeTree(node.left);
      encodeTree(node.right);
  }
  encodeTree(root);
  return strArr.join(',');
};

/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data) {
  let strArr = data.split(',');
  let decodeTree = (strArr) => {
      let ch = strArr.shift();
      if (ch !== '#') {
          let node = new TreeNode(ch);
          node.left = decodeTree(strArr);
          node.right = decodeTree(strArr);
          return node
      } else {
          return null;
      }
  }
  return decodeTree(strArr);
};




// ========================按后序遍历进行序列化与反序列化============================
/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  let strArr = [];
  let encodeTree = (node) => {
      if (!node) {
          strArr.push('#');
          return;
      }
      encodeTree(node.left);
      encodeTree(node.right);
      strArr.push(node.val);

  }
  encodeTree(root);
  return strArr.join(',');
};

/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data) {
  let strArr = data.split(',');
  let decodeTree = (strArr) => {
      let ch = strArr.pop();
      if (ch !== '#') {
          let node = new TreeNode(ch);
          node.right = decodeTree(strArr);
          node.left = decodeTree(strArr);
          return node
      } else {
          return null;
      }
  }
  return decodeTree(strArr);
};


// ========================按中序遍历进行序列化与反序列化============================
/* 
    不可行
  可以进行序列化
  但不能进行反序列化，因为找不到根节点的位置
 */

// ========================按层序遍历进行序列化与反序列化============================
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  if (!root) return '';
  let
      strArr = [],
      queue = [root];
  while (queue.length !== 0) {
      let cur = queue.shift();
      if (cur === null) {
          strArr.push('#');
          continue;
      }
      strArr.push(cur.val);
      queue.push(cur.left);
      queue.push(cur.right);
  }
  return strArr.join(',');
};

/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data) {
  if (!data) return null;
  let
      strArr = data.split(','),
      root = new TreeNode(strArr[0]),
      i = 1;
  queue = [root];
  while(queue.length !== 0) {
      let parent = queue.shift();
      let left_ch = strArr[i];
      i++;
      if(left_ch !== '#') {
          parent.left = new TreeNode(left_ch);
          queue.push(parent.left);
      } else {
          parent.left = null;
      }
      let right_ch = strArr[i];
      i++;
      if(right_ch !== '#') {
          parent.right = new TreeNode(right_ch);
          queue.push(parent.right);
      } else {
          parent.right = null;
      }
  }
  return root;
};